Non-linear Programming¶

Table of contents

  • Task 1
  • Task 2
  • Task 3
  • Task 4
  • Task 5
  • Task 6

Unconstrained optimization¶

Task 1¶

Table of contents
Les oracles suivants sont définis: $$ f_1(x) = x_1^2 + x_2^2 - 2x_1x_2, \nabla f_1 (x) = \left( \begin{array}{c} 2 (x_1-x_2)\\ 2 (x_2-x_1) \end{array} \right) $$ $$ f_2(x) = 10(x_2 - x_1^2)^2 + (1-x_1)^2, \nabla f_2 (x) = \left( \begin{array}{c} -40 x_1(x_2-x_1^2-2(1x_1)\\ 20 (x_2-x_1^2) \end{array} \right) $$ $$ f_3(x) = ||x||_2, \nabla f_3 (x) = \frac{x}{||x||_2} $$

Task 2¶

Table of contents

Gradient descent result - oracle 1 - $x_0=(1,-1)$ - $t=0.5$

The algorithm did not converged in less than 1000 iterations
Last gradient :[-4.  4.]
Last gradient norm:5.656854249492381
Execution time : 0 secondes

Gradient descent result - oracle 2 - $x_0=(1,-1)$ - $t=0.5$

The algorithm diverged after 3 iterations
last gradient:6.432128391102122e+19
The algorithm converged after 3 iterations
optimale solution : [1171561.   15039.] 
minimum : 1.8839076718600384e+25
last gradient:[ 6.43212839e+19 -2.74511032e+13]
Execution time : 0 secondes

Gradient descent result - oracle 3 - $x_0=(1,-1)$ - $t=0.5$

The algorithm did not converged in less than 1000 iterations
Last gradient :[-0.70710678  0.70710678]
Last gradient norm:1.0
Execution time : 0 secondes

Gradient descent result - oracle 3 - $n=10000$ - $t=0.5$

The algorithm did not converged in less than 1000 iterations
Last gradient :[0.01 0.01 0.01 ... 0.01 0.01 0.01]
Last gradient norm:1.000000000000006
Execution time : 0 secondes

Gradient descent result - oracle 1 - $x_0=(1,-1)$ - $t=0.01$

The algorithm did not converged in less than 100 iterations
Last gradient :[ 0.070293 -0.070293]
Last gradient norm:0.0994093101618774
Execution time : 0 secondes

Gradient descent result - oracle 2 - $x_0=(1,-1)$ - $t=0.01$

The algorithm converged after 846 iterations
optimale solution : [0.98893776 0.97755063] 
minimum : 0.00012437359560884338
last gradient:[-0.00443146 -0.00894546]
Execution time : 0 secondes

Gradient descent result - oracle 3 - $x_0=(1,-1)$ - $t=0.01$

The algorithm did not converged in less than 1000 iterations
Last gradient :[ 0.70710678 -0.70710678]
Last gradient norm:1.0
Execution time : 0 secondes

Gradient descent result - oracle 1 - $n=10000$ - $t=0.01$

The algorithm did not converged in less than 1000 iterations
Last gradient :[0.01 0.01 0.01 ... 0.01 0.01 0.01]
Last gradient norm:1.0000000000000075
Execution time : 0 secondes

Task 3¶

Table of contents

Task 4¶

Table of contents

Armijo gradient descent result - oracle 1 - $x_0=(1,-1)$

L'algorithme de descente de gradient avec Armijo a convergé au bout de 157 itérations
solution optimale([ 0.00171519 -0.00171519])
minimum : 1.1767513349899843e-05
dernier gradient:[ 0.00686076 -0.00686076]
Temps d'exécution : 0 secondes

Armijo gradient descent result - oracle 2 - $x_0=(1,-1)$

L'algorithme de descente de gradient avec Armijo a convergé au bout de 1056 itérations
solution optimale([0.98892624 0.97752737])
minimum : 0.00012463282351631437
dernier gradient:[-0.00443617 -0.00895484]
Temps d'exécution : 0 secondes

Armijo gradient descent result - oracle 3 - $x_0=(1,-1)$

L'algorithme de descente de gradient avec Armijo n'a pas convergé en moins de 1000 itérations
dernier gradient:[ 0.70710678 -0.70710678]
norme dernier gradient:1.0
Temps d'exécution : 0 secondes

Task 5¶

Table of contents

Armijo gradient descent result - oracle 4 - $x_0=(10,-10)$

L'algorithme de descente de gradient avec Armijo a convergé au bout de 3827 itérations
solution optimale([-0.00498669  0.00016377])
minimum : 2.4926875252853838e-05
dernier gradient:[-0.00997833  0.00065508]
Temps d'exécution : 0 secondes

Task 6¶

Table of contents $$ \begin{array}{ccc} f_5(x) = ||y-Hx||_2^2, & \nabla f_5(x) = -2 H^{\top}(y-Hx), & \nabla^2f_5(x) = H^{\top}H \end{array} $$ $$ \begin{array}{ccc} min~ f_5(x) & \text{ subject to } ||x||_1\leq \tau & \text{(LASSO)} \end{array} $$ $\mathcal{X} = \{x,||x||_1\leq \tau\}$ is convex because of triangular inequality. $\nabla^2 f_5 > 0$, hence $f_5$ is convex. Therefore (LASSO) problem is convex.

y shape : (255, 1)
H shape : (255, 1024)

Given $c\in \mathbb{R}^n$
For all $x\in \mathbb{R}^n$,
$$ c^{\top}x = \sum_{i=1}^n x_ic_i \geq \sum_{i=1}^n -|x_i||c_i| \geq \sum_{i=1}^n -|x_i|\times||c||_{\infty} = - ||x||_1\times||c||_{\infty} \geq - \tau ||c||_{\infty}, \text{ with } ||c||_{\infty} = \underset{i}{max}|c_i| $$ Note $i^*\in \underset{i}{argmin}|c_i|$, define : $$ x = \left\{ \begin{array}{cc} - sign(c_i^*)\tau & \text{ if } i = i^* \\ 0 & \text{ if } i\neq i^* \end{array} \right. $$ $$ ||x||_1 \leq \tau \text{ and } \forall x'\in \mathbb{R}^n , \text{ s.t } ||x||_1\leq\tau, $$ $$ c^{\top}x' \geq - \tau ||c||_{\infty} = c^{\top}x $$ Hence : $ x\in \underset{x'\leq\tau}{\text{ argmin }} c^{\top}x'$

FW algorithm results - oracle 1 - $x_0=(1,-1)$

L'algorithme de descente de gradient avec Armijo a convergé au bout de 81 itérations
solution optimale([0.02469136 0.        ])
minimum : 0.0006096631611034906
dernier gradient:[ 0.04938272 -0.04938272]
Temps d'exécution : 0 secondes

FW algorithm results - oracle 2 - $x_0=(1,-1)$

L'algorithme de descente de gradient avec Armijo a convergé au bout de 338 itérations
solution optimale([0.93885602 0.8627184 ])
minimum : 0.007247545902868885
dernier gradient:[ 0.58118617 -0.37464432]
Temps d'exécution : 0 secondes

FW algorithm results - oracle 5 - $x_0=0$ - $\tau=20$

L'algorithme de descente de gradient avec Armijo a convergé au bout de 29 itérations
solution optimale([0. 0. 0. ... 0. 0. 0.])
minimum : 19.984431079779835
dernier gradient:[-0.26129367  0.54237418  0.02636319 ... -0.09137482  0.66182451
  0.08082161]
Temps d'exécution : 0 secondes

FW algorithm results - oracle 5 - $x_0=0$ - $\tau=24$

L'algorithme de descente de gradient avec Armijo a convergé au bout de 3728 itérations
solution optimale([0. 0. 0. ... 0. 0. 0.])
minimum : 2.0751600203362655
dernier gradient:[-0.10551591  0.10950759  0.03444799 ...  0.02299265  0.25677155
  0.05000647]
Temps d'exécution : 1 secondes

Result for $\tau = 2$ is saved in X.csv

287.9940335715191
2.0751600203362655